N 皇后 | 秋招知识库

视频讲解

请看【基础算法精讲 16】，制作不易，欢迎点赞关注~

答疑

问：本题和 46. 全排列的关系是什么？

答：由于每行恰好放一个皇后，记录每行的皇后放在哪一列，可以得到一个 $[0, n - 1]$ 的排列 $queens$ 。示例 1 的两个图，分别对应排列 $[1, 3, 0, 2]$ 和 $[2, 0, 3, 1]$ 。所以我们本质上是在枚举列号的全排列。

问：如何 $O (1)$ 判断两个皇后互相攻击？

答：由于我们保证了每行每列恰好放一个皇后，所以只需检查斜方向。对于 ↗ 方向的格子，行号加列号是不变的。对于 ↖ 方向的格子，行号减列号是不变的。如果两个皇后，行号加列号相同，或者行号减列号相同，那么这两个皇后互相攻击。

问：如何 $O (1)$ 判断当前位置被之前放置的某个皇后攻击到？

答：额外用两个数组 ${diag}_{1}$ 和 ${diag}_{2}$ 分别标记之前放置的皇后的行号加列号，以及行号减列号。如果当前位置的行号加列号在 ${diag}_{1}$ 中（标记为 $true$ ），或者当前位置的行号减列号在 ${diag}_{2}$ 中（标记为 $true$ ），那么当前位置被之前放置的皇后攻击到，不能放皇后。

Python 解法1C++ 解法1

python

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        ans = []
        queens = [0] * n  # 皇后放在 (r,queens[r])
        col = [False] * n
        diag1 = [False] * (n * 2 - 1)
        diag2 = [False] * (n * 2 - 1)
        def dfs(r: int) -> None:
            if r == n:
                ans.append(['.' * c + 'Q' + '.' * (n - 1 - c) for c in queens])
                return
            # 在 (r,c) 放皇后
            for c, ok in enumerate(col):
                if not ok and not diag1[r + c] and not diag2[r - c]:  # 判断能否放皇后
                    queens[r] = c  # 直接覆盖，无需恢复现场
                    col[c] = diag1[r + c] = diag2[r - c] = True  # 皇后占用了 c 列和两条斜线
                    dfs(r + 1)
                    col[c] = diag1[r + c] = diag2[r - c] = False  # 恢复现场
        dfs(0)
        return ans

cpp

// C++ 版待补充

C++ 解法2

cpp

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> ans;
        vector board(n, string(n, '.')); // 一开始棋盘是空的，没有皇后
        vector<uint8_t> col(n), diag1(n * 2 - 1), diag2(n * 2 - 1); // vector<uint8_t> 效率比 vector<bool> 高
        auto dfs = [&](this auto&& dfs, int r) {
            if (r == n) {
                ans.push_back(board); // 复制整个棋盘
                return;
            }
            // 在 (r,c) 放皇后
            for (int c = 0; c < n; c++) {
                int rc = r - c + n - 1;
                if (!col[c] && !diag1[r + c] && !diag2[rc]) { // 判断能否放皇后
                    board[r][c] = 'Q'; // 放皇后
                    col[c] = diag1[r + c] = diag2[rc] = true; // 皇后占用了 c 列和两条斜线
                    dfs(r + 1);
                    col[c] = diag1[r + c] = diag2[rc] = false; // 恢复现场
                    board[r][c] = '.';
                }
            }
        };
        dfs(0);
        return ans;
    }
};

C++ 解法3

cpp

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> ans;
        vector<int> queens(n); // 皇后放在 (r,queens[r])
        vector<uint8_t> col(n), diag1(n * 2 - 1), diag2(n * 2 - 1); // vector<uint8_t> 效率比 vector<bool> 高
        auto dfs = [&](this auto&& dfs, int r) {
            if (r == n) {
                vector<string> board(n);
                for (int i = 0; i < n; i++) {
                    board[i] = string(queens[i], '.') + 'Q' + string(n - 1 - queens[i], '.');
                }
                ans.push_back(board);
                return;
            }
            // 在 (r,c) 放皇后
            for (int c = 0; c < n; c++) {
                int rc = r - c + n - 1;
                if (!col[c] && !diag1[r + c] && !diag2[rc]) { // 判断能否放皇后
                    queens[r] = c; // 直接覆盖，无需恢复现场
                    col[c] = diag1[r + c] = diag2[rc] = true; // 皇后占用了 c 列和两条斜线
                    dfs(r + 1);
                    col[c] = diag1[r + c] = diag2[rc] = false; // 恢复现场
                }
            }
        };
        dfs(0);
        return ans;
    }
};

复杂度分析

时间复杂度： $O (n^{2} \cdot n!)$ 。搜索树中至多有 $O (n!)$ 个叶子，每个叶子生成答案每次需要 $O (n^{2})$ 的时间，所以时间复杂度为 $O (n^{2} \cdot n!)$ 。实际上搜索树中远没有这么多叶子， $n = 9$ 时只有 $352$ 种放置方案，远远小于 $9! = 362880$ 。更加准确的方案数可以参考 OEIS A000170，为 $O (\frac{n!}{{2.54}^{n}})$ 。
空间复杂度： $O (n)$ 。返回值的空间不计入。

更多相似题目，见下面回溯题单的「§4.5 排列型回溯」。

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

视频讲解 ​

答疑 ​

复杂度分析 ​

分类题单 ​

视频讲解

答疑

复杂度分析

分类题单